package com.singzi.leetcode.N400;

import java.util.*;

public class T0310 {
}
class Solution0310 {
    List<Integer> list;
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        list = new ArrayList<>();
        int [][]matrix = new int[n][n];
        for(int[] nums: edges){
            matrix[nums[0]][nums[1]] = 1;
            matrix[nums[1]][nums[0]] = 1;
        }
        int []result = new int[n];
        for(int i = 0;i < n;i++){
            result[i] = bfs(matrix,i);
        }
        int min = n;
        for (int i = 0; i < n; i++) {
            if(result[i] < min){
                min = result[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if(result[i] == min) list.add(i);
        }
        return list;
    }

    private int bfs(int[][] matrix, int index) {
        int cnt = 0;
        HashSet<Integer> set = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        int temp;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                temp = queue.remove();
                set.add(temp);
                for(int i = 0;i < matrix.length;i++){
                    if(matrix[temp][i] == 1){
                        if(!set.contains(i)){
                            queue.add(i);
                        }
                    }
                }
                size--;
            }
            cnt++;
        }
        return 0;
    }
}